This article considers recovery of signals that are sparse or approximatelysparse in terms of a (possibly) highly overcomplete and coherent tight framefrom undersampled data corrupted with additive noise. We show that the properlyconstrained $l_1$-analysis, called analysis Dantzig selector, stably recovers asignal which is nearly sparse in terms of a tight frame provided that themeasurement matrix satisfies a restricted isometry property adapted to thetight frame. As a special case, we consider the Gaussian noise. Further, undera sparsity scenario, with high probability, the recovery error from noisy datais within a log-like factor of the minimax risk over the class of vectors whichare at most $s$ sparse in terms of the tight frame. Similar results for theanalysis LASSO are showed. The above two algorithms provide guarantees only for noise that is bounded orbounded with high probability (for example, Gaussian noise). However, when theunderlying measurements are corrupted by sparse noise, these algorithms performsuboptimally. We demonstrate robust methods for reconstructing signals that arenearly sparse in terms of a tight frame in the presence of bounded noisecombined with sparse noise. The analysis in this paper is based on therestricted isometry property adapted to a tight frame, which is a naturalextension to the standard restricted isometry property.
展开▼